// 题目是: 根据字符串的数字组合来穷举出所有的字母组合
// 例如23这个数字组合,所有的字符可能性为: ad , ae , af , bd , be , bf , cd , ce , cf
// 这道题目可以使用广度优先搜索遍历的思路来实现
// 广度优先和二叉树的层序是类似的,我们通过模拟递归来进行对每一个数字所含有的层数进行遍历来组合,最后求出解

// 既然这么做,我们就需要一个映射集来映射每一个数字上面所蕴含的字母,方便我们调用加上遍历

class Solution 
{
public:

    const string digital_mapping [10] = {"" , "" , "abc" , "def" , "ghi" , "jkl" , "mno" , "pqrs" , "tuv" , "wxyz"} ;

    vector<string> result ;

    string path ;

    void backtracking (string digits , int index)
    {

        if (index == digits.size ())
        {

            result.push_back (path) ;

            return ;

        }

        int number = digits [index] - '0' ;

        string letters = digital_mapping [number] ;

        for (int i = 0 ; i < letters.size () ; i++)
        {

            path.push_back (letters [i]) ;

            backtracking (digits , index + 1) ;

            path.pop_back () ;
            
        }

    }

    vector<string> letterCombinations(string digits) 
    {

        if (digits.empty ()) return result ;

        backtracking (digits , 0) ;

        return result ;
        
    }

} ;